1. Field of the Invention
The field of the invention is data processing, or, more specifically, methods, apparatus, and products for executing Multiple Instructions Multiple Data (‘MIMD’) programs on a Single Instruction Multiple Data (‘SIMD’) machine.
2. Description of Related Art
The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely complicated devices. Today's computers are much more sophisticated than early systems such as the EDVAC. Computer systems typically include a combination of hardware and software components, application programs, operating systems, processors, buses, memory, input/output devices, and so on. As advances in semiconductor processing and computer architecture push the performance of the computer higher and higher, more sophisticated computer software has evolved to take advantage of the higher performance of the hardware, resulting in computer systems today that are much more powerful than just a few years ago.
Parallel computing is an area of computer technology that has experienced advances. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. Parallel computing is based on the fact that the process of solving a problem usually can be divided into smaller tasks, which may be carried out simultaneously with some coordination. Parallel computing may be implemented in architectures optimized to execute in a mode of ‘Single Instruction, Multiple Data’ (‘SIMD’) or in a mode of ‘Multiple Instruction, Multiple Data’ (‘MIMD’). This exact terminology, SIMD and MIMD, is from the well-known Flynn's taxonomy, a classification of computer architectures first described by Michael J. Flynn in 1966.
A MIMD machine is a computer in which multiple autonomous processors simultaneously execute different instructions on different data. Distributed systems are generally recognized to be MIMD architectures—either exploiting a single shared memory space or a distributed memory space. Many common computer applications are implemented with MIMD architectures, including, for example, most accounting programs, word processors, spreadsheets, database managers, browsers, web applications, other data communications programs, and so on.
A SIMD machine is a computer that exploits multiple data streams against a single instruction stream to perform operations which may be naturally parallelized. SIMD machines are ubiquitous on a small scale, in digital speech processors, graphics processors, and the like. In addition, however, SIMD machines also make up the largest, most powerful computers in the world. The BlueGene/L computer architecture, for example, is implemented with a SIMD architecture. BlueGene/L installations represent nine of the twenty-five most powerful computer installations in the world—according to a current listing of the top 500 supercomputer sites published by the TOP500 Project. In fact, most, if not all, of the most powerful computers in the world today are SIMD machines.
SIMD machines execute parallel algorithms, typically including collective operations. A parallel algorithm can be split up to be executed a piece at a time on many different processing devices, and then put back together again at the end to get a data processing result. Some algorithms are easy to divide up into pieces. Splitting up the job of checking all of the numbers from one to a hundred thousand to see which are primes could be done, for example, by assigning a subset of the numbers to each available processor, and then putting the list of positive results back together. In this specification, the multiple processing devices that execute the individual pieces of a parallel program are referred to as ‘compute nodes.’ A SIMD machine is composed of compute nodes and other processing nodes as well, including, for example, input/output (‘i/o’) nodes, and service nodes.
Parallel algorithms are designed also to optimize the data communications requirements among the nodes of a SIMD machine. There are two ways parallel processors communicate, shared memory or message passing. Shared memory processing needs additional locking technology for the data and imposes the overhead of additional processor and bus cycles and also serializes some portion of the algorithm. Message passing processing uses high-speed data communications networks and message buffers, but this communication adds transfer overhead on the data communications networks as well as additional memory need for message buffers and latency in the data communications among nodes. Designs of SIMD machines use specially designed data communications links so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.
The large aggregation of data processing power represented by massively parallel SIMD machines is extremely attractive to MIMD applications. The BlueGene/L architecture produces many teraflops per rack, has a large memory footprint, and low power consumption—all features which would make it very useful if MIMD programs could be run on it. MIMD operations, however, require a model that allows for independent programs on each compute. Today the hardware and software for such SIMD machines are designed only to support applications based on cooperating nodes, purely parallel SIMD applications. Specialized memory sharing and data communications technology in SIMD machines, which make the SIMD machines so powerful, render such SIMD machines useless for MIMD applications. In the BlueGene example, a processing error on one node of a partition immediately terminates all data processing operations on every compute node in the partition—a necessary requirement when all the compute nodes are running the same SIMD application—but a disaster for MIMD operations.